package FindMedianSortedArrays


/*
首先，暴力的想法，就是将两个切片进行排序，再将排序的切片进行排序，找到中位数，但是这种方法根据排序的算法，复杂度不同
 */
//第二种方法：
/*
我们可以知道两个切片的长度和，我们就可以知道，合并之后的切片是奇数个还是偶数个。
我们可以使用两个指针进行指向两个切片的中间，用来确定切片中位数
1：首先我们只需要确定第一个切片中位数的指针就可以，因为我们知道合并之后中位数的指针位置，所以我们通过合并之后的中位数指针位置减去第一个切片的中位数指针位置就是第二个切片中位数指针的位置
2：我们先设置两个指针：low,high，我们通过二分法，根据两个切片的中位数指针指向的数值大小，进行low和high的移动，注意low和high都是指向第一个切片的指针，因为知道第一个切片中位数的指针之后，我们就可以知道第二个中位数的指针。
3：通过二分法得到中位数的位置
4：判断合并之后的切片的长度是奇数个还是偶数个
5：如果是偶数个，我们通过指针的左右数字进行判断大小，将四个数进行排序，排序之后，找到中间的两位数， 计算平均数。
6：如果是奇数个，直接返回中间大小的数。
 */

func FindMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	if len(nums1) > len(nums2) {
		return FindMedianSortedArrays(nums2 , nums1)
	}
	low , high , k , mida , midb := 0, len(nums1) , (len(nums1) + len(nums2) + 1) >> 1 , 0 , 0
	for low <= high {
		mida = low + (high - low )>>1
		midb = k - mida
		if mida > 0 && nums1[mida - 1 ] > nums2[midb] {
			high = mida - 1
		} else if mida != len(nums1) && nums2[midb - 1 ] > nums1[mida] {
			low = mida + 1
		} else {
			break
		}
	}
	midleft , midright := 0 , 0
	if mida == 0 {
		midleft = nums2[midb - 1]
	} else if midb == 0 {
		midleft = nums1[mida - 1]
	} else {
		if nums1[mida - 1 ] < nums2[midb - 1] {
			midleft = nums2[midb - 1]
		} else {
			midleft = nums1[mida - 1]
		}
	}
	if (len(nums1) + len(nums2)) & 1 == 1 {
		return float64(midleft)
	}
	if mida == len(nums1) {
		midright = nums2[midb]
	} else if midb == len(nums2) {
		midright = nums1[mida]
	} else {
		if nums2[midb] < nums1[mida] {
			midright = nums2[midb]
		} else {
			midright = nums1[mida]
		}
	}
	return float64(midleft + midright)  / 2
}